public class test {
    //leetcode 1137.第N个泰波那契数
    class Solution {
        public int tribonacci(int n) {
            int n0 = 0;
            int n1 = 1;
            int n2 = 1;
            int num = 0;
            if(n == 0){
                return n0;
            }
            if(n == 1){
                return n1;
            }
            if(n == 2){
                return n2;
            }
            for(int i = 3;i <= n;i++){
                num = n0 + n1 + n2;
                n0 = n1;
                n1 = n2;
                n2 = num;
            }
            return num;
        }
    }
    //leetcode 面试题 08.01 三步问题
    class Solution {
        public int waysToStep(int n) {
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            if (n == 3) {
                return 4;
            }
            int a = 1;
            int b = 2;
            int c = 4;
            int n0 = 0;
            // 3. 填表
            int num = 1000000007;
            for (int i = 4; i <= n; i++) {
                n0 = (((a + b) % num) + c) % num;
                a = b;
                b = c;
                c = n0;
            }
            // 4. 返回值
            return n0;
        }
    }
    //leetcode 746.使用最小花费爬楼梯
    class Solution {
        // 法1.dp[i]表示从0或1位置开始到i位置的最小花费
        public int minCostClimbingStairs(int[] cost) {
            // 1. 创建dp[]表
            int len = cost.length;
            int[] dp = new int[len + 1];
            // 2. 初始化
            dp[0] = 0;
            dp[1] = 0;
            // 3. 填表
            for (int i = 2; i <= len; i++) {
                int n1 = dp[i - 1] + cost[i - 1];
                int n2 = dp[i - 2] + cost[i - 2];
                dp[i] = n1 < n2 ? n1 : n2;
            }
            return dp[len];
        }

        // (cost[0] + cost[2]) < (cost[1] + cost[2]) ? cost[0] + cost[2] : cost[1] +
        // cost[2];
        // 法2.dp[i]表示以i位置开始,到终点的最小花费
        public int minCostClimbingStairs2(int[] cost) {
            // 1. 创建dp[]表
            int len = cost.length;
            int[] dp = new int[len + 1];
            // 2. 初始化
            dp[len] = 0;
            dp[len - 1] = cost[len - 1];
            // 3. 填表
            for (int i = len - 2; i >= 0; i--) {
                dp[i] = Math.min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
            }
            return Math.min(dp[0], dp[1]);
        }
    }
    //leetcode 91.解码方法
    class Solution {
        public int numDecodings(String s) {
            char[] str = s.toCharArray();
            int len = str.length;
            // 1. 创建dp[]表
            // (以i+1位置结尾,有多少种解码方式)(0为虚拟位置,优化代码)
            int[] dp = new int[len+1];
            // 2. 初始化
            dp[0] = 1;//确保dp[2]以后都是正确的
            boolean s1 = str[0] != '0';
            dp[1] = s1 ? 1 : 0;
            if (len == 1) {
                return dp[1];
            }
            // 3. 填表
            for (int i = 2; i <= len; i++) {
                int nn = (str[i - 2] - '0') * 10 + str[i - 1] - '0';
                int n1 = str[i - 1] != '0' ? dp[i - 1] : 0;
                int n2 = nn >= 10 && nn <= 26 ? dp[i - 2] : 0;
                dp[i] += n1;
                dp[i] += n2;
            }
            return dp[len];
        }
    }
    //leetcode 62.不同路径
    class Solution {
        public int uniquePaths(int m, int n) {
            // 1. 创建dp[][]表
            int[][] dp = new int[m+1][n+1];
            // 2. 初始化
            dp[0][0] = 1;
            if((m == 1 && n == 1) || (m == 2 && n == 1) || (m == 1 && n == 2)){
                return 1;
            }
            for(int i = 0;i <= m;i++){
                dp[i][0] = 1;
            }
            for(int i = 0;i <= n;i++){
                dp[0][i] = 1;
            }
            // 3. 填表
            for(int i = 1;i < m;i++){
                for(int j = 1;j < n;j++){
                    int n1 = i - 1 >= 0 ? dp[i-1][j] : 0;
                    int n2 = j - 1 >= 0 ? dp[i][j-1] : 0;
                    dp[i][j] = n1 + n2;
                }
            }
            return dp[m-1][n-1];
        }
    }
}
